11063. B2-последовательность
Последовательность
натуральных чисел 1 £ b1 < b2 < b3 < … называется B2 – последовательностью, если все
попарные суммы bi + bj (i < j) разные.
Необходимо определить, является ли входная последовательность B2 –
последовательностью.
Вход. Первая
строка каждого теста содержит число элементов n (2 £ n £ 100) в последовательности.
Вторая строка содержит саму последовательность b1, b2,
…, bn. Известно, что bi £ 10000. Между тестами присутствует пустая строка.
Выход. Для каждого теста вывести его
номер, начиная с 1, а также сообщение о том, является ли входная
последовательность B2 – последовательностью как показано в примере.
4
1 2 4 8
4
3 7 10 14
Case #1: It is
a B2-Sequence.
Case #2: It is
not a B2-Sequence.
перебор
На этапе чтения
последовательности необходимо проверить, что первый ее элемент не меньше 1, а
каждый следующий строго больший предыдущего (проверка выполнения условия 1 £ b1 < b2
< b3 < …). Далее
перебираем все возможные суммы пар bi
+ bj, запоминаем их в
массиве m (m[bi + bj] = 1) и проверяем тот
факт, что каждая сумма должна встретиться не более одного раза.
Массив m используем для
запоминания всех попарных сумм: m[k]
= 1, если существуют такие элементы bi
и bj, что k = bi
+ bj, иначе m[k] = 0. Элементы bi храним в массиве num.
int m[20001], num[100];
В переменной test содержится номер текущего обрабатываемого теста. Читаем длину
входной последовательности . Обнуляем массив m и переменную-флаг flag.
test = 1;
while(scanf("%d",&n)
== 1)
{
memset(m,0,sizeof(m)); flag = 0; min =
0;
Читаем входную
последовательность. Первый элемент должен быть не меньше 1. Каждый следующий
должен быть строго больше предыдущего. Если одно из этих условий не
выполняется, устанавливаем flag = 1.
for(i = 0; i
< n; i++)
{
scanf("%d",&num[i]);
if (num[i]
<= min) flag = 1; else min = num[i];
}
Перебираем все пары элементов bi и bj, устанавливаем m[bi
+ bj] = 1. Если до выполнения
операции присвоения значение m[bi
+ bj] уже равнялось 1, то
сумма bi + bj уже встречалась. В таком
случае устанавливаем flag = 1.
if (!flag)
for(i = 0; i
< n; i++)
{
for(j = i;
j < n; j++)
if
(m[num[i] + num[j]]) {flag = 1; break;}
else
m[num[i] + num[j]] = 1;
if (flag) break;
}
В зависимости от состояния
переменной flag выводим результат.
if (flag)
printf("Case #%d: It is not a
B2-Sequence.\n\n",test++);
else printf("Case #%d: It is a B2-Sequence.\n\n",test++);
}